"""This module contains numeric manipulation functions related to combinatorics.
"""

"""Project Euler Solutions Library

Copyright (c) 2011 by Robert Vella - robert.r.h.vella@gmail.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""

from euler.numbers.advanced_math import factorial

def number_of_permutations(n, k):
    """Returns the number of permutations for a set of length [n] into smaller
    sets of length [k].
    """
    
    #This is a python implementation of the standard formula for permutations.
    return factorial(n) / factorial(n - k)
    
def number_of_combinations(n, k):
    """Returns the number of combinations for a set of length [n] into smaller
    sets of length [k].
    """
    
    #This is a python implementation of the standard formula for combinations.
    return factorial(n) / (factorial(k) * factorial(n - k))

def lexicographic_permutation_at(items, n):
    """Returns the [n]th lexicographic permutation of [items], with n = 0 being
    the first permutation.
    
    Note: 
        This function uses the array indexes in order to calculate the 
        permutation. Therefore, the content of [items] or the actual
        alphabetical or numerical order of [items] is not taken into account.
        [items] is ordered based on the array indexes.
    """ 
    
    #The length of [items].
    number_of_items = len(items)
    
    #The [n]th permutation of [items].
    permutation_at_n = []
    
    #The indexes in [items].
    indexes = list(xrange(number_of_items))

    #For all index + 1 in [items], starting from the length of items and moving
    #backward.
    for i in range(number_of_items, 0, -1):
        #Get the index of the item at the current position, once this index 
        #is calculated, remove it from the list of indexes.
        relative_index = int(float(n) / factorial(i) * i)
        
        actual_index = indexes[relative_index]
        indexes.remove(actual_index)
        
        permutation_at_n.append(items[actual_index]) 
    
        #Before calculating the remaining positions, update [n] so that it
        #reflects the lexicographic permutation of the remaining indexes. 
        n = n % factorial(i - 1)
        
    return permutation_at_n

def lexicographic_permutations(items):
    """Returns the lexicographic permutations of [items]."""
    number_of_items = len(list(items))
    
    return (lexicographic_permutation_at(items, n) 
            for n in xrange(
                            factorial(number_of_items)
                        )
        )

def count_partitions(integer_to_partition, valid_parts):
    """Returns the number of possible partitions for the given integer,
    and the given parts.
    
    Parameters:
        integer_to_partition - The integer which will be examined.
        valid_parts - The integers which can be summed up to get  
            [integer_to_partition]. 
    """
    
    #Sort the parts to make sure the lowest number is at the 
    #lowest index.
    sorted_parts = valid_parts[:]
    sorted_parts.sort()
    
    def inner_count_partitions(integer_to_partition, index):
        """Returns the number of possible partitions for 
        [integer_to_partition], starting with the part at [index].
        """
        
        #If [integer_to_partition] is equal to 0, the previous
        #reduction operation was valid and therefore should be recorded.
        if integer_to_partition == 0:
            return 1
        
        #If [integer_to_partition] is less than 0, the previous
        #reduction operation was invalid and therefore should not be 
        #recorded.
        elif integer_to_partition < 0:
            return 0
        
        #If there is no part lower than the current one then no
        #more operations should be performed.
        if index < 0:
            return 0
        
        #Get the number of partitions for [integer_to_partition] minus
        #the current part, plus the number of partitions starting from
        #the highest part lower than this one.
        return inner_count_partitions(integer_to_partition, index - 1) + \
                inner_count_partitions(
                                       integer_to_partition - \
                                        sorted_parts[index],
                                       index
                                    ) 
        
    
    return inner_count_partitions(
                                  integer_to_partition,
                                  len(sorted_parts) - 1
                                )



def count_integer_partitions(n, number_of_integers):
    """Returns the number of possible ways in which [n] can be constructed by 
    adding [number_of_integers] integers."""
    
    #Go through all the known cases, and return the value if it is known.
    if number_of_integers == 2:
        return int(n / 2)
    
    if number_of_integers == 3:
        return round((1.0 / 12) * (n ** 2))
    
    if number_of_integers == n:
        return 1
    
    if number_of_integers > n:
        return 0    
    
    if number_of_integers == 0:
        return 0    
    
    #Otherwise calculate the possible ways in which [n - 1] can be constructed 
    #by adding [number_of_integers] integers, and add this number to the number
    #of ways in which [n - number_of_integers] can be constructed by adding
    #[number_of_integers] integers.
    return count_integer_partitions(n - 1, number_of_integers - 1) \
            + count_integer_partitions(
                                       n - number_of_integers,
                                       number_of_integers
                                    )
